class Solution {
public:
  vector<vector<int>> merge(vector<vector<int>>& intervals) {

    map<int, int> m;
    vector<vector<int>> ans;

    if(intervals.empty()){
      return ans;
    }

    for(vector<int> & interval : intervals){   
      if(m.count(interval[0])){
        m[interval[0]] = max(interval[1], m[interval[0]]);
      }else{
        m.insert({interval[0], interval[1]});
      }
    }
    
    vector<int> temp;
    for(map<int, int>::iterator it = m.begin(); it != m.end(); ++it){
      if(it == m.begin()){
        temp.push_back(it->first);
        temp.push_back(it->second);
        continue;
      }
      if(it->first <= temp[1]){
        temp[1] = max(temp[1], it->second);
      }else{
        ans.push_back(temp);
        temp[0] = it->first;
        temp[1] = it->second;
      }
    }
    ans.push_back(temp);

    return ans;

  }
};